package LeetcodeTest_twenty_five;
//865.具有所有最深节点的最小子树

import java.util.HashMap;
import java.util.Scanner;

public class subtreeWithAllDeepest
{
    public static void main(String[] args)
    {
        TreeNode root=new TreeNode();
        root=Solution.createTree(root);
        System.out.println(Solution.subtreeWithAllDeepest(root).val);
    }
}
class Solution
{
    public static TreeNode subtreeWithAllDeepest(TreeNode root)
    {
        if(root.left==null && root.right==null)
            return root;
        HashMap<TreeNode,Integer> map=new HashMap<TreeNode,Integer>();
        map.put(null,0);
        primerSerch(root,map);
        return difs(root,map);
    }
    public static void primerSerch(TreeNode node,HashMap<TreeNode,Integer> map)
    {
        if(node.left==null && node.right==null)
        {
            map.put(node,1);
            return ;
        }
        if(node.left!=null)
        {
            primerSerch(node.left,map);
        }
        else
            map.put(node.left,0);
        if(node.right!=null)
        {
            primerSerch(node.right,map);
        }
        else
            map.put(node.right,0);
        map.put(node, 1 + Math.max(map.get(node.left), map.get(node.right)));
    }
    public static TreeNode difs(TreeNode root,HashMap<TreeNode,Integer> map)
    {
        while(root!=null)
        {
            if(map.get(root.left)==map.get(root.right))
                return root;
            if(map.get(root.left)> map.get(root.right))
            {
                root=root.left;
                if(root.left==null && root.right==null)
                    return root;
            }
            if(map.get(root.left)< map.get(root.right))
            {
                root=root.right;
                if(root.left==null && root.right==null)
                    return root;
            }
        }
        return null;
    }
    public static TreeNode createTree(TreeNode T)
    {
        Scanner reader=new Scanner(System.in);
        int a=reader.nextInt();
        TreeNode p=null;
        if (a==-1)
            p=null;
        else
            p = new TreeNode(a);
        T=p;
        if(T==null)
            return T;
        else
        {
            T.left = createTree(T.left);
            T.right = createTree(T.right);
        }
        return T;
    }
}
class TreeNode
{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}